//Longest Increasing Subsequence

#include<iostream>
using namespace std;

int a[] = {1,3,7,2,3,4,5};
int ls[1+sizeof(a)/sizeof(int)];
int lis(int i);
void findlis(int j);
void lis()
{
	// Initializing array ls to -1
	for(int i=0; i<=sizeof(a)/sizeof(int); i++)
	ls[i] = -1;
	
	
	for(int i=0; i<=sizeof(a)/sizeof(int); i++)
	lis(i);
	int j=0;
	int max = 0;
	for(int i=0; i<=sizeof(a)/sizeof(int); i++)
	{
		if(max <= ls[i])
		{
			j = i;
			max = ls[i];
		}
	}
	//findlis(j);
	//cout << ":" << a[j-1];
	cout << "\n" << j << "The max is : " << max << "\n";
	return;
}

int main()
{
	lis();
	return 0;
}

int lis(int i)
{
	
	if(i==0 || i==1)
	{
		ls[i] = i;
		return ls[i];
	}
	if(ls[i]!=-1)
	return ls[i];
	
	int max = 0;
	for(int j=0; j<i-1; j++)
	{
		if(a[i-1]>a[j])
		max = max>ls[j+1]?max:ls[j+1];
	}
	ls[i] = 1+max;
	return ls[i];
}

void findlis(int j)
{
	cout << "\n::Welcome to here.\n";
	if(j==0)
	return;
	
	if(j==1)
	{
		cout << a[0];
		return;
	}
	int i = j-1;
	for (i = j; ls[i] != ls[j]-1;)
	i--;
	findlis(i);
	cout << "\n" << i << "::" << a[i-1] << "\n";
	return;
}
